package Top_Interview_Questions_Review._001Tree;

import Top_Interview_Questions_Review._001Tree.Supple.TreeNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/10 13:25
 * <p>
 * 功能描述:
 */
public class _0098 {

    public static void main(String[] args) {
        _0098 test = new _0098();
        test.isValidBST2(null);

//        TreeNode root = new TreeNode(10);
//        TreeNode node1 = new TreeNode(5);
//        TreeNode node2 = new TreeNode(15);
//        TreeNode node3 = new TreeNode(11);
//        TreeNode node4 = new TreeNode(20);
//        TreeNode node5 = new TreeNode(17);
//        TreeNode node6 = new TreeNode(22);
//
//        root.left = node1;
//        root.right = node2;
//        node2.left = node3;
//        node2.right = node4;
//        node4.left = node5;
//        node4.right = node6;
//        System.out.println(test.isValidBST(root));
    }



    /*--------------------------------------解法一-------------------------------------------*/

    public boolean isValidBST1(TreeNode root) {
        if (root == null)
            return true;
        ReturnData returnData = process(root);
        return returnData.isBST;
    }

    public static class ReturnData {
        //整颗树是不是BST
        public boolean isBST;
        //整颗树的最小值
        public int min;
        //整颗树的最大值
        public int max;

        public ReturnData(boolean is, int mi, int ma) {
            isBST = is;
            min = mi;
            max = ma;
        }
    }

    //以x为root的树，返回ReturnData三个信息
    public static ReturnData process(TreeNode x) {
        if (x == null) {
            return null;
        }
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);

        int min = x.val;
        int max = x.val;
        if (leftData != null) {
            //左树上的最小值，和我现在的最小值比较一下，哪个小就是哪个，后面同理
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }

        boolean isBST = false;
        //最后去判断整棵树是不是BST。分别判断左右子树
        if ((leftData != null ? (leftData.isBST && leftData.max < x.val) : true)
                && (rightData != null ? (rightData.isBST && rightData.min > x.val) : true)) {
            isBST = true;
        }

        return new ReturnData(isBST, min, max);
    }

    /*--------------------------------------解法一-------------------------------------------*/


    /*-------------------------------------化简解法一-----------------------------------------*/

    /**
     * https://gitee.com/youthlql/fucking-algorithm
     * 数据结构系列，二叉树操作集锦里有讲为什么要这样遍历
     * <p>
     *        10
     *      /   \
     *     5    15
     *        /   \
     *       11   20
     *           /  \
     *         17   22
     */
    public boolean isValidBST(TreeNode root) {

        return helper(root, null, null);
    }


    /**
     * 功能描述:
     * 1、由上面的判断我们可以看到，对于以root为根节点的树。左子树只需要获取最大值，右子树需要获取最小值
     */
    boolean helper(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null)
            return true;
        //判断右子树
        if (min != null && root.val <= min.val)
            return false;
        //root是上一层的左子树，max就是上一层的节点值。左子树的值如果>=上一层节点值，说明不是BST
        if (max != null && root.val >= max.val)
            return false;
        return helper(root.left, min, root) && helper(root.right, root, max);
    }

//
//    if ((leftData != null ? (leftData.isBST && leftData.max < x.val) : true)
//            && (rightData != null ? (rightData.isBST && rightData.min > x.val) : true)) {
//        isBST = true;
//    }

    /*-------------------------------------中序遍历-----------------------------------------*/

    TreeNode pre = null;
    boolean flag = true;

    public boolean isValidBST2(TreeNode root) {

        helper(root);
        return flag;
    }

    public  void helper(TreeNode root){
        if(root == null)
            return;
        helper(root.left);

        if(pre != null && pre.val >= root.val)
            flag = false;

        pre = root;

        helper(root.right);
    }


}
